/*
 * 给你一个整数数组 nums，有一个大小为 k
 * 的滑动窗口从数组的最左侧移动到数组的最右侧。 你只可以看到在滑动窗口内的 k
 * 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。
 *
 * 示例 1：
 *   输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
 *   输出：[3,3,5,5,6,7]
 *   解释：
 *     滑动窗口的位置                最大值
 *     ---------------               -----
 *     [1  3  -1] -3  5  3  6  7       3
 *      1 [3  -1  -3] 5  3  6  7       3
 *      1  3 [-1  -3  5] 3  6  7       5
 *      1  3  -1 [-3  5  3] 6  7       5
 *      1  3  -1  -3 [5  3  6] 7       6
 *      1  3  -1  -3  5 [3  6  7]      7
 *
 * 示例 2：
 *
 *   输入：nums = [1], k = 1
 *   输出：[1]
 *
 * 提示：
 *
 *   1 <= nums.length <= 105
 *   -104 <= nums[i] <= 104
 *   1 <= k <= nums.length
 */

#include <stdio.h>
#include <stdlib.h>

int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize) {
    int q[numsSize];
    int left = 0, right = 0;
    for (int i = 0; i < k; ++i) {
        while (left < right && nums[i] >= nums[q[right - 1]]) {
            right--;
        }
        q[right++] = i;
    }
    *returnSize = 0;
    int* ans = malloc(sizeof(int) * (numsSize - k + 1));
    ans[(*returnSize)++] = nums[q[left]];
    for (int i = k; i < numsSize; ++i) {
        while (left < right && nums[i] >= nums[q[right - 1]]) {
            right--;
        }
        q[right++] = i;
        while (q[left] <= i - k) {
            left++;
        }
        ans[(*returnSize)++] = nums[q[left]];
    }
    return ans;
}

int main() {
  int nums[] = {1,3,-1,-3,5,3,6,7};
  int k = 3;
  int n = sizeof(nums) / sizeof(nums[0]);
  int returnSize;
  int* result = maxSlidingWindow(nums, n, k, &returnSize);

  printf("Max sliding window: ");
  int i;
  for (i = 0; i < returnSize; ++i) {
    printf("%d ", result[i]);
  }
  printf("\n");

  free(result);
  return 0;
}
